//二叉树实现的插入排序
package gopl

import "fmt"

type tree struct {
	value       int
	left, right *tree
}

var ToSort = []int{4, 6, 3, 2, 7, 1}

func Sort(values []int) {
	var root *tree
	for _, v := range values {
		root = add(root, v)
	}

	//排序完成，要将二叉树整理输出
	// 先输出左子树，输出节点，输出右子树
	// 只能是递归
	showTree(root)
}

func showTree(t *tree) {
	if t.left != nil {
		showTree(t.left)
	}
	fmt.Println(t.value, "\t")
	if t.right != nil {
		showTree(t.right)
	}
}

func add(t *tree, value int) *tree {
	if t == nil {
		t = new(tree)
		t.value = value
		return t
	}
	if value < t.value {
		t.left = add(t.left, value)
	} else {
		t.right = add(t.right, value)
	}
	return t
}
